package com.linchong.dynamicprogramming.easy;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-19 10:40
 * @Description: HouseRobber$198-打家劫舍-https://leetcode-cn.com/problems/house-robber/
 */
public class HouseRobber {

	/**
	 *
	 * 序列型动态规划，最多偷多少金币，问前N栋房子，最多偷多少
	 *
	 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
	 *
	 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
	 *
	 *  
	 *示例 1：
	 *
	 * 输入：[1,2,3,1]
	 * 输出：4
	 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
	 *      偷窃到的最高金额 = 1 + 3 = 4 。
	 * 示例 2：
	 *
	 * 输入：[2,7,9,3,1]
	 * 输出：12
	 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
	 *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
	 *  
	 *
	 * 提示：
	 *
	 * 0 <= nums.length <= 100
	 * 0 <= nums[i] <= 400
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/house-robber
	 *
	 *
	 * step 1:确定状态
	 *  最后一步：最优策略中，有可能偷或者不偷最后一个房子N-1
	 *      第一种情况：不偷房子N-1
	 *          简单，最优策略就是前N-1栋房子的最优策略
	 *      第二种情况：偷房子N-1
	 *          此时需要知道前N-1栋房子能偷多少金币，同时保证不偷第N-2栋房子
	 *
	 *      如何在不偷第N-2栋房子的前提下，获得在前N-1栋房子中最多能偷的金币呢？
	 *         f[i][0]表示不偷房子i-1的情况下，获得的最大的金币，有
	 *
	 *              f[i][0] = max{f[i-1][0],f[i-1][1]}  ====>  f[i] = max{f[i-1][0],f[i-1][1]}
	 *              不偷房子i-1,房子i-2可以选择偷或者不偷
	 *
	 *         f[i][1]表示偷房子i-1的情况下，获得的最大金币
	 *
	 *              f[i][1] = f[i-1][0] + A[i-1]  ====》 f[i] = f[i-2]+A[i-1]
	 *              偷房子i-1,房子i-2必须不偷
	 *        综上可以简化：
	 *
	 *          设f[i]为窃贼在前i栋房子最多偷的金币
	 *              f[i] = max{f[i-1],f[i-2]+A[i-1]}
	 * step 2 状态转移方程：
	 *              f[i] = max{f[i-1],f[i-2]+A[i-1]}
	 *
	 * step 3 边界和初始值
	 *          初始条件：
	 *              f[0]=0,没有房子，偷0枚金币
	 *              f[1] = A[0]
	 *              f[2] = max{A[0],A[1]}
	 *
	 *step 4 计算顺序
	 *
	 *      初始化f[0]
	 *      计算： f[0],f[1],f[2]...f[n]
	 *
	 *      结果为f[n]
	 *
	 *      时间复杂度O(n)，空间复杂度O(1){i-1与i-2中获得，不用开辟长度为n的数组}
	 *
	 */

	public int rob(int[] nums) {

		int n = nums.length;
		if(n==0){
			return 0;
		}

		int[] f = new int[n+1];

		f[0] = 0;
		f[1] = nums[0];

		for (int i = 2; i <= n; i++) {
			f[i] = Math.max(f[i-1],f[i-2]+nums[i-1]);
		}

		return f[n];


	}
	public static void main(String[] args) {
		int[] nums = {2,7,9,3,1};
		HouseRobber instance = new HouseRobber();
		System.out.println(instance.rob(nums));
	}
}
